# Definition for a Node.
class Node:
  def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
    self.val = int(x)
    self.next = next
    self.random = random


class Solution:
  def copyRandomList(self, head: 'Node') -> 'Node':
    import collections
    if not head:
      return None
    head_sav = head
    new_head = Node(x=head.val)
    new_head_sav, new_head_sav_2 = new_head, new_head
    hash_map = collections.OrderedDict()
    node_map = collections.OrderedDict()
    count = 0
    while head:
      if head.next:
        new_head.next = Node(x=head.next.val)
      else:
        new_head.next = None
      hash_map[count] = new_head
      node_map[head] = count
      count = count + 1
      head = head.next
      new_head = new_head.next
    # 给hash_map和node_map都补上一个空值
    hash_map[count] = None
    node_map[None] = count
    while head_sav:
      new_head_sav.random = hash_map[node_map.get(head_sav.random)]
      head_sav = head_sav.next
      new_head_sav = new_head_sav.next
    return new_head_sav_2


  def printLinkList(self, head: 'Node') -> list:
    while head:
      print(head.val, end='->')
      head = head.next


'''
STATUS: SOLVED
TRIES:  1
TIME:   44 MS
MEMORY: 14.2 MB
'''
if __name__ == "__main__":
  import collections
  solution = Solution()
